{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению. Сессия № 2\n",
    "\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Основные метрики качества классификации\n",
    "\n",
    "[Статья](https://habrahabr.ru/company/ods/blog/328372/) на Хабре по этой теме. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Матрица ошибок\n",
    "Существует множество различных числовых характеристик, позволяющих измерить качество бинарного классификатора. В случае двух классов возможны всего 4 исхода при классификации данного объекта. Их удобно отображать с помощью матрицы ошибок (confusion matrix).Это таблица с двумя строками и двумя столбцами, в ячейках которой указаны следующие значения:\n",
    "- $TP$ = число верно классифицированных положительных примеров\n",
    "- $FP$ = число отрицательных примеров, классифицированных положительно (ошибки первого рода)\n",
    "- $TN$ = число верно классифицированных отрицательных примеров\n",
    "- $FN$ = число положительных примеров, классифицированных отрицательно (ошибки второго рода)\n",
    "\n",
    "<center>\n",
    "<img src=\"../../img/contingency.png\" width = \"500\">\n",
    "</center>\n",
    "\n",
    "Получить такую таблицу можно с помощью функции sklearn.metrics.confusion_matrix, передав ей на вход истинные и предсказанные классификатором метки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import seaborn as sns\n",
    "from sklearn import metrics\n",
    "\n",
    "true_labels = np.array([0, 1, 0, 0, 1, 1, 1, 1])\n",
    "predicted_labels = np.array([0, 1, 1, 0, 0, 1, 0, 0])\n",
    "\n",
    "M = metrics.confusion_matrix(true_labels, predicted_labels)\n",
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Характеристики бинарного классификатора\n",
    "Основываясь на данной таблице, можно ввести несколько величин, характеризующих бинарный классификатор:\n",
    "$$rec = TPR = \\frac{TP}{TP + FN},\\quad SPC = \\frac{TN}{TN + FP},\\quad prec = PPV = \\frac{TP}{TP + FP},\\quad FPR = 1 - SPC,$$\n",
    "\n",
    "$$ACC = \\frac{TP + TN}{TP + TN + FP + FN},\\quad F1 = 2\\frac{PPV\\cdot TRP}{PPV + TPR}.$$\n",
    "\n",
    "Полнота $TPR$ (True positive rate, recall, sensitivity) - доля верно классифицированных положительных примеров среди всех положительных примеров.\n",
    "\n",
    "Специфичность $SPC$ (Specificity, true negative rate) - доля верно классифицированных отрицательных примеров среди всех отрицательных примеров.\n",
    "\n",
    "Точность $PPV$ (Positive predictive value, precision) - доля верно классифицированных положительных примеров среди всех примеров, классифицированных положительно.\n",
    "\n",
    "$FPR$ (False positive rate) - доля ошибочно классифицированных отрицательных примеров среди всех отрицательных примеров.\n",
    "\n",
    "$ACC$ (Accuracy) - доля верно классифицированных примеров среди всех примеров. Основная характеристика качества классификации.\n",
    "\n",
    "$F1$ (F1-measure) - среднее гармоническое точности и полноты. Позволяет учесть обе характеристики одновременно.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PPV = metrics.precision_score(true_labels, predicted_labels)\n",
    "TPR = metrics.recall_score(true_labels, predicted_labels)\n",
    "F1 = metrics.f1_score(true_labels, predicted_labels)\n",
    "ACC = metrics.accuracy_score(true_labels, predicted_labels)\n",
    "PPV, TPR, F1, ACC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ROC-кривая и AUC\n",
    "\n",
    "Большинство бинарных классификаторов имеют вид $a(x) = \\mbox{sign}(f(x, w) - w_0)$, где $w, w_0$ - параметры алгоритма. То есть сначала строится разделяющая поверхность $f(x, w) = w_0$, после чего объекты, находяющиеся по одну сторону от неё классифицируются положительно, по другую - отрицательно. \n",
    "\n",
    "ROC-кривая (Receiver Operating Characteristic) - это графическая характеристика качества бинарного классификатора, выражающая зависимость TPR от FPR при варьировании порога решающего правила. Она наглядно представляет, каким будет качество классификации при различных значениях $w_0$ и фиксированном значении $w$. \n",
    "\n",
    "ROC-кривая проходит через точки (0, 0) и (1, 1) и монотонно не убывает. Чем ближе кривая внутри квадрата $[0, 1]\\times[0, 1]$ к левому верхнему углу, тем лучше. Идеальный вариант - кривая, проходящая через три точки: (0, 0), (1, 1) и (0, 1). Диагональ данного квадрата соответствует случайному гаданию. Типичная ROC-кривая для классификатора соответствует кривой B на рисунке.\n",
    "<center>\n",
    "<img src=\"../../img/ROC.jpg\" width = \"350\">\n",
    "</center>\n",
    "На практике ROC-кривую всегда оценивают по независимой тестовой выборке, для того чтобы избежать переобучения.\n",
    "\n",
    "Площадь под ROC-кривой AUC (Area Under Curve) является количественной характеристикой качества классификации, не зависящей от соотношения цен ошибок. Чем больше значение AUC, тем «лучше» модель классификации. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Случай дисбаланса классов\n",
    "\n",
    "Возможные [действия](http://machinelearningmastery.com/tactics-to-combat-imbalanced-classes-in-your-machine-learning-dataset/):\n",
    "- Собрать больше данных, особенно примеров редкого класса (не всегда возможно)\n",
    "- Использовать методы, основанные на деревьях решений  - случайный лес, градиентный бустинг над деревьями. Деревья не так подвержены проблеме дисбаланса классов\n",
    "- Использовать метрики типа F1, ROC AUC и [Cohen's kappa](https://en.wikipedia.org/wiki/Cohen%27s_kappa), а не accuracy\n",
    "- Использовать метрику, в которой ошибка на объекте из редкого класса входит с большим весом, чем ошибка на объекте из частого класса\n",
    "- Применять [oversampling](https://en.wikipedia.org/wiki/Oversampling_and_undersampling_in_data_analysis) и [undersampling](https://en.wikipedia.org/wiki/Oversampling_and_undersampling_in_data_analysis). В первом случае в выборку добавляются представители редкого класса (сэмплируются с замещением). Во втором - представители частого класса случайным образом удаляются из выборки\n",
    "- Сгенерировать искусственных представителей редкого класса. [SMOTE](http://www.jair.org/papers/paper953.html) (Synthetic Minority Over-sampling Technique). [Реализация](https://github.com/fmfn/UnbalancedDataset) на Python\n",
    "- Разбить один большой класс на несколько поменьше и применить стратегии One Vs. All или One Vs. One\n",
    "- Применить алгоритмы поиска выбросов или OneClass алгоритмы (например, OneClass SVM)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Примеры"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "from sklearn.svm import SVC, LinearSVC\n",
    "\n",
    "if sys.version_info.major == 2:\n",
    "    from urllib import urlopen\n",
    "elif sys.version_info.major == 3:\n",
    "    from urllib.request import urlopen\n",
    "\n",
    "from sklearn import datasets\n",
    "from sklearn.metrics import auc, roc_curve\n",
    "from sklearn.model_selection import cross_val_score, train_test_split\n",
    "from sklearn.multiclass import OneVsRestClassifier\n",
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loading Pima Indians Diabetes data from UCI Machine learning repository\n",
    "url = \"https://archive.ics.uci.edu/ml/machine-learning-databases/pima-indians-diabetes/pima-indians-diabetes.data\"\n",
    "raw_data = urlopen(url)\n",
    "data = np.loadtxt(raw_data, delimiter=\",\")\n",
    "\n",
    "X = data[:, :8]\n",
    "y = data[:, 8]\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)\n",
    "C = 10.0  # Regularization parameter of the error term\n",
    "\n",
    "lin_svm = LinearSVC(C=C, dual=False).fit(X_train, y_train)\n",
    "y_score = lin_svm.decision_function(X_test)\n",
    "\n",
    "# Compute ROC curve and ROC area\n",
    "fpr, tpr, _ = roc_curve(y_test, y_score)\n",
    "roc_auc = auc(fpr, tpr)\n",
    "\n",
    "# Plot of a ROC curve for a specific class\n",
    "plt.figure()\n",
    "plt.plot(fpr, tpr, label=\"ROC curve (area = %0.2f)\" % roc_auc)\n",
    "plt.plot([0, 1], [0, 1], \"k--\")\n",
    "plt.xlim([0.0, 1.0])\n",
    "plt.ylim([0.0, 1.05])\n",
    "plt.xlabel(\"False Positive Rate\")\n",
    "plt.ylabel(\"True Positive Rate\")\n",
    "plt.title(\"Receiver operating characteristic example\")\n",
    "plt.legend(loc=\"lower right\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Указанные выше характеристики можно использовать для подбора параметров алгоритмов, например, с помощью кросс-валидации. Найдём оптимальное с точки зрения F1-меры число ближайших соседей в алгоритме kNN."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn = KNeighborsClassifier()\n",
    "k_s = np.arange(1, 50, 2)\n",
    "\n",
    "scores_f1 = list()\n",
    "\n",
    "for k in k_s:\n",
    "    knn.n_neighbors = k\n",
    "    scores_f1.append(np.mean(cross_val_score(knn, X, y, scoring=\"f1\")))\n",
    "\n",
    "plt.figure(1, figsize=(10, 5))\n",
    "plt.clf()\n",
    "plt.plot(k_s, scores_f1, linewidth=2)\n",
    "plt.axvline(k_s[np.argmax(scores_f1)], color=\"r\")\n",
    "plt.ylabel(\"F1-score\")\n",
    "plt.xlabel(\"Parameter k\")\n",
    "plt.xlim(1, 49)\n",
    "plt.title(\"F1-optimal number of neighbors, $k$ = %d\" % k_s[np.argmax(scores_f1)])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Многоклассовая классификация\n",
    "В случае, когда число классов больше двух, матрица ошибок определяется аналогичным образом: на пересечении $i$-ой строки и $j$-го столбца стоит число примеров $i$-го класса, отнесённых классификатором к классу $j$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "true_labels = np.array([0, 1, 2, 0, 1, 2, 0, 1, 2])\n",
    "predicted_labels = np.array([0, 2, 0, 2, 1, 0, 0, 1, 2])\n",
    "\n",
    "M = metrics.confusion_matrix(true_labels, predicted_labels)\n",
    "M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### One vs. All\n",
    "Многоклассовая классификация может быть сведена к бинарной различными способами. Одним из них является подход One vs. All. Его суть в следующем: для каждого класса $i \\in \\{1, \\dots, k\\}$ обучим бинарный классификатор $a_i(x) = \\mbox{sign}f_i(x)$ на исходной выборке с изменёнными метками (объекты $i$-го класса получают метку 1, все оставшиеся объекты - метку 0), то есть мы учим $a_i$ отличать $i$-ый класс от всех остальных. После чего итоговый классификатор строится как $a(x) = \\mbox{argmax}_{i \\in \\{1, \\dots, k\\}} f_i(x)$, то есть он выдаёт класс с наибольшей оценкой $f_i(x)$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = datasets.load_iris()\n",
    "X, y = iris.data, iris.target\n",
    "# Fitting One vs. All version of linear SVM\n",
    "onevsall = OneVsRestClassifier(LinearSVC()).fit(X, y)\n",
    "metrics.accuracy_score(y, onevsall.predict(X))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cсылки:\n",
    "\n",
    "- [Статья](http://habrahabr.ru/post/228963/) \"Как заставить работать бинарный классификатор чуточку лучше\" на Habrahabr\n",
    "- [ROC-кривая](http://www.machinelearning.ru/wiki/index.php?title=ROC-%D0%BA%D1%80%D0%B8%D0%B2%D0%B0%D1%8F)\n",
    "- [Характеристики](https://en.wikipedia.org/wiki/Precision_and_recall) бинарного классификатора\n",
    "- [One vs. All и One vs. One](https://en.wikipedia.org/wiki/Multiclass_classification)\n",
    "- [Quora](https://www.quora.com/In-classification-how-do-you-handle-an-unbalanced-training-set) про несбаланированные выборки\n",
    "- про несбаланированные выборки на [ресурсе](http://machinelearningmastery.com/tactics-to-combat-imbalanced-classes-in-your-machine-learning-dataset/) Machine Learning Mastery"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
